{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Santa的接待安排  \n",
    "圣诞节前100天，Santa开放了workshop，欢迎以家庭单位的参观，如何更合理的安排这些家庭参观？  \n",
    "每个家庭有10个选择choice0-9，数字代表了距离圣诞节的天数，比如 1代表12月24日，每个家庭必须并且只安排一次参观  \n",
    "家庭数量 5000，即family_id 为[0, 4999]，每天访问的人数需要在125-300人"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:24.347430Z",
     "start_time": "2020-11-29T07:01:22.903348Z"
    }
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "from ortools.linear_solver import pywraplp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. 数据加载"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:24.415434Z",
     "start_time": "2020-11-29T07:01:24.351430Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>choice_0</th>\n",
       "      <th>choice_1</th>\n",
       "      <th>choice_2</th>\n",
       "      <th>choice_3</th>\n",
       "      <th>choice_4</th>\n",
       "      <th>choice_5</th>\n",
       "      <th>choice_6</th>\n",
       "      <th>choice_7</th>\n",
       "      <th>choice_8</th>\n",
       "      <th>choice_9</th>\n",
       "      <th>n_people</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>family_id</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>52</td>\n",
       "      <td>38</td>\n",
       "      <td>12</td>\n",
       "      <td>82</td>\n",
       "      <td>33</td>\n",
       "      <td>75</td>\n",
       "      <td>64</td>\n",
       "      <td>76</td>\n",
       "      <td>10</td>\n",
       "      <td>28</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>26</td>\n",
       "      <td>4</td>\n",
       "      <td>82</td>\n",
       "      <td>5</td>\n",
       "      <td>11</td>\n",
       "      <td>47</td>\n",
       "      <td>38</td>\n",
       "      <td>6</td>\n",
       "      <td>66</td>\n",
       "      <td>61</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>100</td>\n",
       "      <td>54</td>\n",
       "      <td>25</td>\n",
       "      <td>12</td>\n",
       "      <td>27</td>\n",
       "      <td>82</td>\n",
       "      <td>10</td>\n",
       "      <td>89</td>\n",
       "      <td>80</td>\n",
       "      <td>33</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>2</td>\n",
       "      <td>95</td>\n",
       "      <td>1</td>\n",
       "      <td>96</td>\n",
       "      <td>32</td>\n",
       "      <td>6</td>\n",
       "      <td>40</td>\n",
       "      <td>31</td>\n",
       "      <td>9</td>\n",
       "      <td>59</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>53</td>\n",
       "      <td>1</td>\n",
       "      <td>47</td>\n",
       "      <td>93</td>\n",
       "      <td>26</td>\n",
       "      <td>3</td>\n",
       "      <td>46</td>\n",
       "      <td>16</td>\n",
       "      <td>42</td>\n",
       "      <td>39</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>32</td>\n",
       "      <td>59</td>\n",
       "      <td>12</td>\n",
       "      <td>3</td>\n",
       "      <td>60</td>\n",
       "      <td>26</td>\n",
       "      <td>35</td>\n",
       "      <td>50</td>\n",
       "      <td>5</td>\n",
       "      <td>2</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>88</td>\n",
       "      <td>4</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>91</td>\n",
       "      <td>32</td>\n",
       "      <td>39</td>\n",
       "      <td>57</td>\n",
       "      <td>28</td>\n",
       "      <td>99</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>25</td>\n",
       "      <td>11</td>\n",
       "      <td>52</td>\n",
       "      <td>48</td>\n",
       "      <td>10</td>\n",
       "      <td>17</td>\n",
       "      <td>88</td>\n",
       "      <td>50</td>\n",
       "      <td>95</td>\n",
       "      <td>66</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>18</td>\n",
       "      <td>60</td>\n",
       "      <td>1</td>\n",
       "      <td>12</td>\n",
       "      <td>89</td>\n",
       "      <td>33</td>\n",
       "      <td>16</td>\n",
       "      <td>10</td>\n",
       "      <td>53</td>\n",
       "      <td>67</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>1</td>\n",
       "      <td>88</td>\n",
       "      <td>39</td>\n",
       "      <td>50</td>\n",
       "      <td>26</td>\n",
       "      <td>18</td>\n",
       "      <td>96</td>\n",
       "      <td>47</td>\n",
       "      <td>46</td>\n",
       "      <td>28</td>\n",
       "      <td>7</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "           choice_0  choice_1  choice_2  choice_3  choice_4  choice_5  \\\n",
       "family_id                                                               \n",
       "0                52        38        12        82        33        75   \n",
       "1                26         4        82         5        11        47   \n",
       "2               100        54        25        12        27        82   \n",
       "3                 2        95         1        96        32         6   \n",
       "4                53         1        47        93        26         3   \n",
       "5                32        59        12         3        60        26   \n",
       "6                88         4         1         3        91        32   \n",
       "7                25        11        52        48        10        17   \n",
       "8                18        60         1        12        89        33   \n",
       "9                 1        88        39        50        26        18   \n",
       "\n",
       "           choice_6  choice_7  choice_8  choice_9  n_people  \n",
       "family_id                                                    \n",
       "0                64        76        10        28         4  \n",
       "1                38         6        66        61         4  \n",
       "2                10        89        80        33         3  \n",
       "3                40        31         9        59         2  \n",
       "4                46        16        42        39         4  \n",
       "5                35        50         5         2         4  \n",
       "6                39        57        28        99         2  \n",
       "7                88        50        95        66         5  \n",
       "8                16        10        53        67         4  \n",
       "9                96        47        46        28         7  "
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = pd.read_csv('./family_data.csv',index_col='family_id')\n",
    "data.head(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. 数据预处理  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.1 preference cost  \n",
    "  代表Santa的个性化安排能力,数据如下面的表格"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-28T11:43:14.199483Z",
     "start_time": "2020-11-28T11:43:14.185482Z"
    }
   },
   "source": [
    "| 安排       | 礼品卡    |  每个家庭成员  |\n",
    "| -------- | ----- | ---- |\n",
    "|Choice_0 |不需要 | 不需要 |\n",
    "|Choice_1 |\\$50 | 不需要 |\n",
    "|Choice_2 |\\$50 | \\$9 |\n",
    "|Choice_3 |\\$100 | \\$9 |\n",
    "|Choice_4 |\\$200 | \\$9 |\n",
    "|Choice_5 |\\$200 | \\$18 |\n",
    "|Choice_6 |\\$300 | \\$18 |\n",
    "|Choice_7 |\\$300 | \\$36 |\n",
    "|Choice_8 |\\$400 | \\$36 |\n",
    "|Choice_9 |\\$500 | \\$36+\\$199 |\n",
    "|otherwise |\\$50 | \\$36+\\$398 |\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下面是，根据上面的表格的数据，计算5000个家庭安排到100天中的cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:24.429435Z",
     "start_time": "2020-11-29T07:01:24.419434Z"
    }
   },
   "outputs": [],
   "source": [
    "#n代表家庭成员个数，如果满足第choice需求，需要的penalty\n",
    "def get_penalty(n, choice):\n",
    "    if choice == 0:\n",
    "        penalty  =0\n",
    "    if choice == 1:\n",
    "        penalty = 50\n",
    "    if choice == 2:\n",
    "        penalty = 50 + 9*n\n",
    "    if choice == 3:\n",
    "        penalty = 100 + 9 * n\n",
    "    if choice == 4:\n",
    "        penalty = 200 + 9 * n\n",
    "    if choice == 5:\n",
    "        penalty = 200 + 18 * n\n",
    "    if choice == 6:\n",
    "        penalty = 300 + 18 * n\n",
    "    if choice == 7:\n",
    "        penalty = 300 + 36 * n\n",
    "    if choice == 8:\n",
    "        penalty = 400 + 36 * n\n",
    "    if choice == 9:\n",
    "        penalty = 500 + (36 +199)* n\n",
    "    if choice >9:\n",
    "        penalty = 500 + (36 +398)* n\n",
    "\n",
    "    return penalty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:24.440436Z",
     "start_time": "2020-11-29T07:01:24.433435Z"
    }
   },
   "outputs": [],
   "source": [
    "N_FAMILY = 5000   #5000个家庭\n",
    "N_DAY =100        #100天\n",
    "N_CHOICE=10       #10个选择\n",
    "\n",
    "#创建5000*100的nd array数组，用来存放安排成本，初始值为999999\n",
    "pcost_matrix = np.full(shape=(N_FAMILY,N_DAY), fill_value=999999)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:28.526669Z",
     "start_time": "2020-11-29T07:01:24.444436Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[2236, 2236, 2236, ..., 2236, 2236, 2236],\n",
       "       [2236, 2236, 2236, ..., 2236, 2236, 2236],\n",
       "       [1802, 1802, 1802, ..., 1802, 1802,    0],\n",
       "       ...,\n",
       "       [3104, 3104,  616, ..., 3104, 3104, 3104],\n",
       "       [ 390, 2670, 2670, ..., 2670, 2670, 2670],\n",
       "       [2236, 2236, 2236, ..., 2236, 2236, 2236]])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for i in range(N_FAMILY):\n",
    "    n_people = data.iloc[i,10]\n",
    "    pcost_matrix[i,:] =  get_penalty(n_people,10)\n",
    "    for j in range(N_CHOICE):\n",
    "        day = data.iloc[i, j] - 1\n",
    "        pcost_matrix[i,day] = get_penalty(n_people,j)\n",
    "pcost_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:28.536670Z",
     "start_time": "2020-11-29T07:01:28.529669Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([2236, 2236, 2236, 2236, 2236, 2236, 2236, 2236, 2236,  544, 2236,\n",
       "         86, 2236, 2236, 2236, 2236, 2236, 2236, 2236, 2236, 2236, 2236,\n",
       "       2236, 2236, 2236, 2236, 2236, 1440, 2236, 2236, 2236, 2236,  236,\n",
       "       2236, 2236, 2236, 2236,   50, 2236, 2236, 2236, 2236, 2236, 2236,\n",
       "       2236, 2236, 2236, 2236, 2236, 2236, 2236,    0, 2236, 2236, 2236,\n",
       "       2236, 2236, 2236, 2236, 2236, 2236, 2236, 2236,  372, 2236, 2236,\n",
       "       2236, 2236, 2236, 2236, 2236, 2236, 2236, 2236,  272,  444, 2236,\n",
       "       2236, 2236, 2236, 2236,  136, 2236, 2236, 2236, 2236, 2236, 2236,\n",
       "       2236, 2236, 2236, 2236, 2236, 2236, 2236, 2236, 2236, 2236, 2236,\n",
       "       2236])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pcost_matrix[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-28T12:27:11.386532Z",
     "start_time": "2020-11-28T12:27:11.234523Z"
    }
   },
   "source": [
    "2.2 accounting penalty  \n",
    "代表Santa安排的财务成本\n",
    "每天接待的人员数N(d)如果大于125，就会拥挤，产生过多的清洁成本，计算公式为  \n",
    "![avatar]()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:28.757682Z",
     "start_time": "2020-11-29T07:01:28.540670Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.00000000e+00, 0.00000000e+00, 0.00000000e+00, ...,\n",
       "        0.00000000e+00, 0.00000000e+00, 0.00000000e+00],\n",
       "       [0.00000000e+00, 0.00000000e+00, 0.00000000e+00, ...,\n",
       "        0.00000000e+00, 0.00000000e+00, 0.00000000e+00],\n",
       "       [0.00000000e+00, 0.00000000e+00, 0.00000000e+00, ...,\n",
       "        0.00000000e+00, 0.00000000e+00, 0.00000000e+00],\n",
       "       ...,\n",
       "       [4.16316072e+15, 3.71482922e+15, 3.31477861e+15, ...,\n",
       "        7.46610759e+00, 8.36716954e+00, 9.37697794e+00],\n",
       "       [4.79555148e+15, 4.27883100e+15, 3.81778713e+15, ...,\n",
       "        8.43020770e+00, 7.52185316e+00, 8.43020770e+00],\n",
       "       [5.52415954e+15, 4.92860244e+15, 4.39725208e+15, ...,\n",
       "        9.51970597e+00, 8.49339085e+00, 7.57772228e+00]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#计算accouting penalty矩阵,相邻两天的所有可能的结果的财务成本都算出来\n",
    "MIN_OCCUPANCY=125\n",
    "MAX_OCCUPANCY=300\n",
    "\n",
    "acost_matrix = np.zeros(shape=(MAX_OCCUPANCY+1, MAX_OCCUPANCY+1))\n",
    "\n",
    "for i in range(acost_matrix.shape[0]):     #当天安排的人数\n",
    "    for j in range(acost_matrix.shape[1]): #前一天安排的人数\n",
    "        diff = abs(i-j)\n",
    "        acost_matrix[i,j] =max(0, (i-125) / 400 * i **(0.5 + diff/50.0))\n",
    "acost_matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. 使用LP和MIP求解 规划方案"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:59.441437Z",
     "start_time": "2020-11-29T07:01:28.760683Z"
    }
   },
   "outputs": [],
   "source": [
    "#GLOP线性规划器\n",
    "solver = pywraplp.Solver('AssignmentProblem', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)\n",
    "x={}      #family_id在第j天是否参观\n",
    "\n",
    "candidates = [[] for i in range(N_DAY)]    #每一天的参观家庭的候选集\n",
    "\n",
    "#每个家庭的期望参观日\n",
    "DISIRED=data.values[:,:-1]-1\n",
    "\n",
    "for i in range(N_FAMILY):\n",
    "    for j in DISIRED[i, :]:\n",
    "        candidates[j].append(i)  #在第j天有第2个家庭想参加\n",
    "        #定义决策变量，第i个家庭在第j天是否参观\n",
    "        x[i,j]=solver.BoolVar('x[%i,%i]' %(i,j))\n",
    "\n",
    "#定义目标函数preference cost部分,每个家庭在所有期望日的成本累加\n",
    "preference_cost= solver.Sum(x[i,j] * pcost_matrix[i,j] for i in range(N_FAMILY) for j in DISIRED[i,:])\n",
    "\n",
    "#满足preference cost最小\n",
    "solver.Minimize((preference_cost))\n",
    "\n",
    "#增加约束条件1，前后两天的人数不多余25人\n",
    "FAMILY_SIZE=data['n_people'].values\n",
    "daily_occupancy =[solver.Sum(x[i,j] * FAMILY_SIZE[i] for i in candidates[j]) for j in range(N_DAY)]\n",
    "\n",
    "for j in range(N_DAY-1):   #j代表当天，j+1代表前一天\n",
    "    solver.Add(daily_occupancy[j]-daily_occupancy[j+1]<=25)  \n",
    "    solver.Add(daily_occupancy[j+1]-daily_occupancy[j]<=25)\n",
    "    \n",
    "#加约束条件2，每个家庭在choice里只出现1次    \n",
    "family_presence = [solver.Sum(x[i,j] for j in DISIRED[i,:]) for i in range(N_FAMILY)]\n",
    "for i in range(N_FAMILY):\n",
    "    solver.Add(family_presence[i]==1)\n",
    "\n",
    "#加约束条件3，每天访问人数\n",
    "for j in range(N_DAY):\n",
    "    solver.Add(daily_occupancy[j]>=MIN_OCCUPANCY)\n",
    "    solver.Add(daily_occupancy[j]<=MAX_OCCUPANCY)\n",
    "\n",
    "result = solver.Solve()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:59.603447Z",
     "start_time": "2020-11-29T07:01:59.443438Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 51, 1.0),\n",
       " (1, 25, 1.0),\n",
       " (2, 99, 0.9999999999999999),\n",
       " (3, 1, 1.0),\n",
       " (4, 52, 1.0),\n",
       " (5, 31, 1.0),\n",
       " (6, 87, 1.0),\n",
       " (7, 24, 1.0),\n",
       " (8, 17, 1.0),\n",
       " (9, 49, 1.0),\n",
       " (10, 91, 1.0),\n",
       " (11, 18, 1.0),\n",
       " (12, 97, 1.0),\n",
       " (13, 53, 1.0),\n",
       " (14, 44, 1.0),\n",
       " (15, 21, 1.0),\n",
       " (16, 45, 1.0),\n",
       " (17, 46, 1.0),\n",
       " (18, 74, 0.9999999999999999),\n",
       " (19, 2, 1.0),\n",
       " (20, 2, 1.0),\n",
       " (21, 55, 1.0),\n",
       " (22, 60, 1.0),\n",
       " (23, 18, 0.9999999999999999),\n",
       " (24, 74, 1.0),\n",
       " (25, 15, 0.9999999999999999),\n",
       " (26, 57, 1.0),\n",
       " (27, 37, 1.0),\n",
       " (28, 26, 1.0),\n",
       " (29, 7, 1.0),\n",
       " (30, 67, 0.9999999999999999),\n",
       " (31, 73, 0.9999999999999999),\n",
       " (32, 23, 0.9999999999999999),\n",
       " (33, 31, 0.9999999999999999),\n",
       " (34, 45, 0.9999999999999999),\n",
       " (35, 30, 0.9999999999999999),\n",
       " (36, 46, 1.0),\n",
       " (37, 14, 1.0),\n",
       " (38, 12, 1.0),\n",
       " (39, 8, 1.0),\n",
       " (40, 24, 1.0),\n",
       " (41, 91, 1.0),\n",
       " (42, 80, 1.0),\n",
       " (43, 10, 1.0),\n",
       " (44, 48, 1.0),\n",
       " (45, 4, 1.0),\n",
       " (46, 14, 1.0),\n",
       " (47, 44, 1.0),\n",
       " (48, 31, 1.0),\n",
       " (49, 32, 1.0),\n",
       " (50, 49, 1.0),\n",
       " (51, 27, 1.0),\n",
       " (52, 32, 1.0),\n",
       " (53, 36, 1.0),\n",
       " (54, 68, 0.9999999999999999),\n",
       " (55, 90, 0.9999999999999999),\n",
       " (56, 11, 1.0),\n",
       " (57, 30, 1.0),\n",
       " (58, 73, 1.0),\n",
       " (59, 38, 0.25000000000000155),\n",
       " (59, 14, 0.7499999999999984),\n",
       " (60, 97, 1.0),\n",
       " (61, 17, 1.0),\n",
       " (62, 38, 1.0),\n",
       " (63, 62, 1.0),\n",
       " (64, 2, 0.9999999999999999),\n",
       " (65, 46, 1.0),\n",
       " (66, 0, 1.0),\n",
       " (67, 20, 1.0),\n",
       " (68, 84, 1.0),\n",
       " (69, 21, 1.0),\n",
       " (70, 31, 1.0),\n",
       " (71, 70, 1.0),\n",
       " (72, 65, 0.9999999999999999),\n",
       " (73, 9, 1.0),\n",
       " (74, 27, 1.0),\n",
       " (75, 52, 1.0),\n",
       " (76, 78, 1.0),\n",
       " (77, 19, 1.0),\n",
       " (78, 51, 1.0),\n",
       " (79, 36, 1.0),\n",
       " (80, 17, 1.0),\n",
       " (81, 16, 1.0),\n",
       " (82, 31, 1.0),\n",
       " (83, 87, 1.0),\n",
       " (84, 8, 1.0),\n",
       " (85, 53, 0.9999999999999999),\n",
       " (86, 28, 0.9999999999999999),\n",
       " (87, 24, 1.0),\n",
       " (88, 56, 1.0),\n",
       " (89, 22, 1.0),\n",
       " (90, 53, 1.0),\n",
       " (91, 16, 1.0),\n",
       " (92, 84, 1.0),\n",
       " (93, 4, 1.0),\n",
       " (94, 46, 1.0),\n",
       " (95, 23, 1.0),\n",
       " (96, 74, 1.0),\n",
       " (97, 47, 1.0),\n",
       " (98, 2, 1.0),\n",
       " (99, 38, 0.9999999999999999),\n",
       " (100, 38, 1.0),\n",
       " (101, 52, 1.0),\n",
       " (102, 28, 1.0),\n",
       " (103, 67, 1.0),\n",
       " (104, 46, 1.0),\n",
       " (105, 11, 1.0),\n",
       " (106, 33, 1.0),\n",
       " (107, 11, 1.0),\n",
       " (108, 33, 1.0),\n",
       " (109, 16, 1.0),\n",
       " (110, 21, 1.0),\n",
       " (111, 67, 1.0),\n",
       " (112, 12, 1.0),\n",
       " (113, 17, 1.0),\n",
       " (114, 14, 1.0),\n",
       " (115, 21, 1.0),\n",
       " (116, 76, 1.0),\n",
       " (117, 93, 1.0),\n",
       " (118, 68, 1.0),\n",
       " (119, 3, 1.0),\n",
       " (120, 55, 1.0),\n",
       " (121, 16, 0.9999999999999999),\n",
       " (122, 23, 1.0),\n",
       " (123, 21, 1.0),\n",
       " (124, 13, 1.0),\n",
       " (125, 46, 1.0),\n",
       " (126, 2, 1.0),\n",
       " (127, 1, 1.0),\n",
       " (128, 55, 1.0),\n",
       " (129, 42, 1.0),\n",
       " (130, 15, 1.0),\n",
       " (131, 10, 1.0),\n",
       " (132, 75, 1.0),\n",
       " (133, 53, 1.0),\n",
       " (134, 17, 1.0),\n",
       " (135, 4, 1.0),\n",
       " (136, 87, 1.0),\n",
       " (137, 81, 1.0),\n",
       " (138, 1, 1.0),\n",
       " (139, 88, 0.9999999999999999),\n",
       " (140, 12, 1.0),\n",
       " (141, 88, 1.0),\n",
       " (142, 25, 1.0),\n",
       " (143, 37, 0.9999999999999999),\n",
       " (144, 27, 1.0),\n",
       " (145, 17, 1.0),\n",
       " (146, 63, 0.9999999999999999),\n",
       " (147, 27, 1.0),\n",
       " (148, 62, 1.0),\n",
       " (149, 60, 1.0),\n",
       " (150, 59, 1.0),\n",
       " (151, 2, 1.0),\n",
       " (152, 87, 1.0),\n",
       " (153, 2, 1.0),\n",
       " (154, 24, 1.0),\n",
       " (155, 99, 1.0),\n",
       " (156, 43, 1.0),\n",
       " (157, 86, 0.9999999999999999),\n",
       " (158, 12, 1.0),\n",
       " (159, 54, 1.0),\n",
       " (160, 39, 1.0),\n",
       " (161, 46, 1.0),\n",
       " (162, 85, 1.0),\n",
       " (163, 83, 1.0),\n",
       " (164, 17, 1.0),\n",
       " (165, 96, 1.0),\n",
       " (166, 83, 1.0),\n",
       " (167, 92, 1.0),\n",
       " (168, 18, 1.0),\n",
       " (169, 66, 1.0),\n",
       " (170, 11, 1.0),\n",
       " (171, 23, 1.0),\n",
       " (172, 20, 1.0),\n",
       " (173, 54, 1.0),\n",
       " (174, 33, 1.0),\n",
       " (175, 16, 1.0),\n",
       " (176, 51, 1.0),\n",
       " (177, 12, 1.0),\n",
       " (178, 79, 1.0),\n",
       " (179, 25, 1.0),\n",
       " (180, 19, 1.0),\n",
       " (181, 6, 0.9999999999999999),\n",
       " (182, 93, 1.0),\n",
       " (183, 16, 0.9999999999999999),\n",
       " (184, 3, 1.0),\n",
       " (185, 79, 1.0),\n",
       " (186, 49, 1.0),\n",
       " (187, 42, 1.0),\n",
       " (188, 9, 0.9999999999999999),\n",
       " (189, 50, 0.9999999999999999),\n",
       " (190, 8, 1.0),\n",
       " (191, 53, 1.0),\n",
       " (192, 76, 0.9999999999999999),\n",
       " (193, 34, 1.0),\n",
       " (194, 94, 1.0),\n",
       " (195, 54, 0.9999999999999999),\n",
       " (196, 99, 1.0),\n",
       " (197, 58, 1.0),\n",
       " (198, 89, 1.0),\n",
       " (199, 50, 1.0),\n",
       " (200, 25, 1.0),\n",
       " (201, 34, 1.0),\n",
       " (202, 22, 1.0),\n",
       " (203, 37, 1.0),\n",
       " (204, 66, 1.0),\n",
       " (205, 0, 1.0),\n",
       " (206, 27, 1.0),\n",
       " (207, 46, 1.0),\n",
       " (208, 9, 1.0),\n",
       " (209, 70, 1.0),\n",
       " (210, 22, 1.0),\n",
       " (211, 66, 1.0),\n",
       " (212, 9, 0.9999999999999999),\n",
       " (213, 51, 1.0),\n",
       " (214, 30, 0.9999999999999999),\n",
       " (215, 0, 1.0),\n",
       " (216, 42, 1.0),\n",
       " (217, 4, 1.0),\n",
       " (218, 37, 1.0),\n",
       " (219, 67, 1.0),\n",
       " (220, 0, 1.0),\n",
       " (221, 16, 1.0),\n",
       " (222, 35, 1.0),\n",
       " (223, 59, 1.0),\n",
       " (224, 3, 1.0),\n",
       " (225, 60, 1.0),\n",
       " (226, 58, 1.0),\n",
       " (227, 48, 1.0),\n",
       " (228, 86, 1.0),\n",
       " (229, 47, 1.0),\n",
       " (230, 56, 1.0),\n",
       " (231, 47, 1.0),\n",
       " (232, 46, 0.9999999999999999),\n",
       " (233, 86, 1.0),\n",
       " (234, 81, 1.0),\n",
       " (235, 52, 0.9999999999999999),\n",
       " (236, 36, 1.0),\n",
       " (237, 2, 1.0),\n",
       " (238, 18, 1.0),\n",
       " (239, 13, 0.9999999999999999),\n",
       " (240, 32, 0.7499999999999782),\n",
       " (240, 56, 0.25000000000002176),\n",
       " (241, 59, 1.0),\n",
       " (242, 59, 1.0),\n",
       " (243, 88, 1.0),\n",
       " (244, 34, 1.0),\n",
       " (245, 12, 1.0),\n",
       " (246, 49, 1.0),\n",
       " (247, 65, 1.0),\n",
       " (248, 32, 1.0),\n",
       " (249, 13, 1.0),\n",
       " (250, 6, 1.0),\n",
       " (251, 96, 1.0),\n",
       " (252, 17, 1.0),\n",
       " (253, 72, 1.0),\n",
       " (254, 17, 1.0),\n",
       " (255, 11, 1.0),\n",
       " (256, 92, 1.0),\n",
       " (257, 73, 1.0),\n",
       " (258, 91, 1.0),\n",
       " (259, 59, 1.0),\n",
       " (260, 36, 1.0),\n",
       " (261, 82, 0.9999999999999999),\n",
       " (262, 31, 0.500000000000001),\n",
       " (262, 34, 0.499999999999999),\n",
       " (263, 47, 0.9999999999999999),\n",
       " (264, 10, 1.0),\n",
       " (265, 10, 1.0),\n",
       " (266, 31, 1.0),\n",
       " (267, 17, 1.0),\n",
       " (268, 38, 1.0),\n",
       " (269, 29, 1.0),\n",
       " (270, 66, 1.0),\n",
       " (271, 54, 1.0),\n",
       " (272, 42, 1.0),\n",
       " (273, 37, 1.0),\n",
       " (274, 7, 0.9999999999999999),\n",
       " (275, 14, 1.0),\n",
       " (276, 68, 1.0),\n",
       " (277, 2, 0.9999999999999999),\n",
       " (278, 53, 0.9999999999999999),\n",
       " (279, 37, 1.0),\n",
       " (280, 22, 1.0),\n",
       " (281, 21, 0.9999999999999999),\n",
       " (282, 16, 0.9999999999999999),\n",
       " (283, 8, 1.0),\n",
       " (284, 19, 1.0),\n",
       " (285, 4, 1.0),\n",
       " (286, 53, 1.0),\n",
       " (287, 46, 1.0),\n",
       " (288, 62, 1.0),\n",
       " (289, 65, 1.0),\n",
       " (290, 55, 1.0),\n",
       " (291, 79, 1.0),\n",
       " (292, 65, 0.9999999999999999),\n",
       " (293, 22, 1.0),\n",
       " (294, 45, 1.0),\n",
       " (295, 9, 1.0),\n",
       " (296, 38, 1.0),\n",
       " (297, 47, 1.0),\n",
       " (298, 49, 0.9999999999999999),\n",
       " (299, 31, 1.0),\n",
       " (300, 4, 1.0),\n",
       " (301, 44, 1.0),\n",
       " (302, 3, 1.0),\n",
       " (303, 26, 0.9999999999999999),\n",
       " (304, 85, 1.0),\n",
       " (305, 57, 1.0),\n",
       " (306, 1, 1.0),\n",
       " (307, 31, 1.0),\n",
       " (308, 46, 1.0),\n",
       " (309, 18, 1.0),\n",
       " (310, 63, 1.0),\n",
       " (311, 58, 1.0),\n",
       " (312, 42, 1.0),\n",
       " (313, 36, 1.0),\n",
       " (314, 38, 1.0),\n",
       " (315, 44, 1.0),\n",
       " (316, 52, 1.0),\n",
       " (317, 24, 0.9999999999999999),\n",
       " (318, 48, 1.0),\n",
       " (319, 9, 1.0),\n",
       " (320, 6, 1.0),\n",
       " (321, 94, 1.0),\n",
       " (322, 81, 1.0),\n",
       " (323, 47, 1.0),\n",
       " (324, 32, 1.0),\n",
       " (325, 0, 1.0),\n",
       " (326, 25, 1.0),\n",
       " (327, 45, 1.0),\n",
       " (328, 9, 0.9999999999999999),\n",
       " (329, 18, 1.0),\n",
       " (330, 92, 1.0),\n",
       " (331, 16, 1.0),\n",
       " (332, 9, 1.0),\n",
       " (333, 22, 1.0),\n",
       " (334, 21, 1.0),\n",
       " (335, 67, 1.0),\n",
       " (336, 88, 1.0),\n",
       " (337, 23, 1.0),\n",
       " (338, 73, 1.0),\n",
       " (339, 44, 1.0),\n",
       " (340, 12, 1.0),\n",
       " (341, 57, 0.9999999999999999),\n",
       " (342, 53, 1.0),\n",
       " (343, 88, 0.9999999999999999),\n",
       " (344, 29, 1.0),\n",
       " (345, 65, 1.0),\n",
       " (346, 0, 1.0),\n",
       " (347, 58, 1.0),\n",
       " (348, 4, 1.0),\n",
       " (349, 18, 1.0),\n",
       " (350, 73, 1.0),\n",
       " (351, 26, 1.0),\n",
       " (352, 92, 1.0),\n",
       " (353, 24, 1.0),\n",
       " (354, 26, 1.0),\n",
       " (355, 84, 1.0),\n",
       " (356, 50, 1.0),\n",
       " (357, 24, 0.4625000000000049),\n",
       " (357, 54, 0.5374999999999951),\n",
       " (358, 10, 1.0),\n",
       " (359, 89, 1.0),\n",
       " (360, 54, 1.0),\n",
       " (361, 33, 1.0),\n",
       " (362, 80, 0.9999999999999999),\n",
       " (363, 11, 1.0),\n",
       " (364, 98, 0.9999999999999999),\n",
       " (365, 3, 1.0),\n",
       " (366, 92, 1.0),\n",
       " (367, 16, 1.0),\n",
       " (368, 92, 1.0),\n",
       " (369, 71, 1.0),\n",
       " (370, 92, 1.0),\n",
       " (371, 25, 1.0),\n",
       " (372, 97, 1.0),\n",
       " (373, 8, 1.0),\n",
       " (374, 74, 1.0),\n",
       " (375, 5, 1.0),\n",
       " (376, 25, 1.0),\n",
       " (377, 81, 1.0),\n",
       " (378, 24, 0.9999999999999999),\n",
       " (379, 64, 1.0),\n",
       " (380, 98, 1.0),\n",
       " (381, 26, 1.0),\n",
       " (382, 47, 1.0),\n",
       " (383, 11, 1.0),\n",
       " (384, 2, 1.0),\n",
       " (385, 28, 1.0),\n",
       " (386, 14, 1.0),\n",
       " (387, 38, 1.0),\n",
       " (388, 31, 1.0),\n",
       " (389, 53, 1.0),\n",
       " (390, 39, 1.0),\n",
       " (391, 52, 1.0),\n",
       " (392, 59, 1.0),\n",
       " (393, 35, 1.0),\n",
       " (394, 10, 1.0),\n",
       " (395, 7, 1.0),\n",
       " (396, 71, 0.9999999999999999),\n",
       " (397, 51, 1.0),\n",
       " (398, 36, 1.0),\n",
       " (399, 4, 1.0),\n",
       " (400, 2, 1.0),\n",
       " (401, 51, 1.0),\n",
       " (402, 62, 1.0),\n",
       " (403, 16, 1.0),\n",
       " (404, 47, 1.0),\n",
       " (405, 53, 1.0),\n",
       " (406, 2, 1.0),\n",
       " (407, 67, 1.0),\n",
       " (408, 20, 1.0),\n",
       " (409, 80, 1.0),\n",
       " (410, 80, 0.9999999999999999),\n",
       " (411, 82, 1.0),\n",
       " (412, 24, 1.0),\n",
       " (413, 61, 1.0),\n",
       " (414, 25, 1.0),\n",
       " (415, 23, 1.0),\n",
       " (416, 95, 1.0),\n",
       " (417, 9, 0.9999999999999999),\n",
       " (418, 31, 1.0),\n",
       " (419, 25, 1.0),\n",
       " (420, 59, 1.0),\n",
       " (421, 68, 0.9999999999999999),\n",
       " (422, 23, 1.0),\n",
       " (423, 73, 1.0),\n",
       " (424, 3, 1.0),\n",
       " (425, 29, 1.0),\n",
       " (426, 35, 1.0),\n",
       " (427, 23, 1.0),\n",
       " (428, 39, 1.0),\n",
       " (429, 1, 1.0),\n",
       " (430, 4, 1.0),\n",
       " (431, 14, 1.0),\n",
       " (432, 44, 1.0),\n",
       " (433, 0, 1.0),\n",
       " (434, 61, 1.0),\n",
       " (435, 0, 1.0),\n",
       " (436, 10, 1.0),\n",
       " (437, 63, 1.0),\n",
       " (438, 24, 1.0),\n",
       " (439, 5, 1.0),\n",
       " (440, 38, 1.0),\n",
       " (441, 32, 1.0),\n",
       " (442, 28, 1.0),\n",
       " (443, 13, 0.9999999999999999),\n",
       " (444, 25, 1.0),\n",
       " (445, 73, 0.9999999999999999),\n",
       " (446, 26, 1.0),\n",
       " (447, 18, 1.0),\n",
       " (448, 81, 1.0),\n",
       " (449, 17, 1.0),\n",
       " (450, 59, 1.0),\n",
       " (451, 32, 0.9999999999999999),\n",
       " (452, 86, 1.0),\n",
       " (453, 50, 1.0),\n",
       " (454, 10, 0.9999999999999999),\n",
       " (455, 2, 1.0),\n",
       " (456, 25, 1.0),\n",
       " (457, 69, 0.9999999999999999),\n",
       " (458, 45, 1.0),\n",
       " (459, 65, 1.0),\n",
       " (460, 29, 1.0),\n",
       " (461, 26, 1.0),\n",
       " (462, 57, 1.0),\n",
       " (463, 70, 1.0),\n",
       " (464, 45, 1.0),\n",
       " (465, 45, 1.0),\n",
       " (466, 35, 1.0),\n",
       " (467, 2, 1.0),\n",
       " (468, 41, 1.0),\n",
       " (469, 92, 1.0),\n",
       " (470, 16, 1.0),\n",
       " (471, 37, 1.0),\n",
       " (472, 13, 1.0),\n",
       " (473, 55, 0.9999999999999999),\n",
       " (474, 21, 1.0),\n",
       " (475, 32, 1.0),\n",
       " (476, 53, 1.0),\n",
       " (477, 59, 1.0),\n",
       " (478, 4, 1.0),\n",
       " (479, 33, 1.0),\n",
       " (480, 77, 0.9999999999999999),\n",
       " (481, 71, 1.0),\n",
       " (482, 29, 1.0),\n",
       " (483, 77, 1.0),\n",
       " (484, 25, 1.0),\n",
       " (485, 29, 1.0),\n",
       " (486, 10, 1.0),\n",
       " (487, 25, 0.9999999999999999),\n",
       " (488, 39, 0.5000000000000305),\n",
       " (488, 6, 0.49999999999996947),\n",
       " (489, 15, 1.0),\n",
       " (490, 27, 1.0),\n",
       " (491, 72, 1.0),\n",
       " (492, 94, 0.9999999999999999),\n",
       " (493, 15, 1.0),\n",
       " (494, 94, 1.0),\n",
       " (495, 55, 1.0),\n",
       " (496, 55, 1.0),\n",
       " (497, 15, 1.0),\n",
       " (498, 70, 1.0),\n",
       " (499, 45, 1.0),\n",
       " (500, 26, 1.0),\n",
       " (501, 20, 1.0),\n",
       " (502, 55, 1.0),\n",
       " (503, 21, 1.0),\n",
       " (504, 80, 1.0),\n",
       " (505, 15, 1.0),\n",
       " (506, 37, 1.0),\n",
       " (507, 12, 1.0),\n",
       " (508, 34, 1.0),\n",
       " (509, 36, 1.0),\n",
       " (510, 81, 1.0),\n",
       " (511, 42, 1.0),\n",
       " (512, 57, 1.0),\n",
       " (513, 63, 1.0),\n",
       " (514, 2, 0.9999999999999999),\n",
       " (515, 13, 1.0),\n",
       " (516, 41, 1.0),\n",
       " (517, 59, 0.9999999999999999),\n",
       " (518, 23, 1.0),\n",
       " (519, 23, 1.0),\n",
       " (520, 3, 0.9999999999999999),\n",
       " (521, 65, 1.0),\n",
       " (522, 31, 1.0),\n",
       " (523, 3, 1.0),\n",
       " (524, 73, 1.0),\n",
       " (525, 18, 1.0),\n",
       " (526, 58, 1.0),\n",
       " (527, 15, 1.0),\n",
       " (528, 99, 1.0),\n",
       " (529, 24, 1.0),\n",
       " (530, 60, 1.0),\n",
       " (531, 44, 0.9999999999999999),\n",
       " (532, 3, 1.0),\n",
       " (533, 25, 1.0),\n",
       " (534, 13, 1.0),\n",
       " (535, 71, 1.0),\n",
       " (536, 90, 1.0),\n",
       " (537, 22, 1.0),\n",
       " (538, 82, 1.0),\n",
       " (539, 8, 1.0),\n",
       " (540, 30, 0.9999999999999999),\n",
       " (541, 85, 1.0),\n",
       " (542, 21, 1.0),\n",
       " (543, 52, 0.9999999999999999),\n",
       " (544, 11, 1.0),\n",
       " (545, 78, 1.0),\n",
       " (546, 79, 1.0),\n",
       " (547, 59, 1.0),\n",
       " (548, 87, 1.0),\n",
       " (549, 43, 0.9999999999999999),\n",
       " (550, 72, 1.0),\n",
       " (551, 2, 1.0),\n",
       " (552, 34, 1.0),\n",
       " (553, 44, 1.0),\n",
       " (554, 52, 0.9999999999999999),\n",
       " (555, 9, 1.0),\n",
       " (556, 97, 1.0),\n",
       " (557, 15, 1.0),\n",
       " (558, 19, 1.0),\n",
       " (559, 46, 1.0),\n",
       " (560, 17, 1.0),\n",
       " (561, 19, 0.9999999999999999),\n",
       " (562, 26, 1.0),\n",
       " (563, 75, 1.0),\n",
       " (564, 81, 1.0),\n",
       " (565, 90, 1.0),\n",
       " (566, 44, 1.0),\n",
       " (567, 75, 1.0),\n",
       " (568, 79, 1.0),\n",
       " (569, 24, 1.0),\n",
       " (570, 10, 0.9999999999999999),\n",
       " (571, 97, 1.0),\n",
       " (572, 61, 1.0),\n",
       " (573, 76, 1.0),\n",
       " (574, 62, 1.0),\n",
       " (575, 93, 1.0),\n",
       " (576, 80, 0.9999999999999999),\n",
       " (577, 30, 1.0),\n",
       " (578, 17, 1.0),\n",
       " (579, 76, 1.0),\n",
       " (580, 48, 1.0),\n",
       " (581, 41, 1.0),\n",
       " (582, 19, 1.0),\n",
       " (583, 34, 1.0),\n",
       " (584, 86, 0.9999999999999999),\n",
       " (585, 2, 1.0),\n",
       " (586, 77, 1.0),\n",
       " (587, 7, 1.0),\n",
       " (588, 50, 1.0),\n",
       " (589, 81, 1.0),\n",
       " (590, 89, 1.0),\n",
       " (591, 54, 1.0),\n",
       " (592, 39, 1.0),\n",
       " (593, 22, 1.0),\n",
       " (594, 60, 1.0),\n",
       " (595, 18, 1.0),\n",
       " (596, 87, 1.0),\n",
       " (597, 80, 1.0),\n",
       " (598, 46, 1.0),\n",
       " (599, 42, 1.0),\n",
       " (600, 14, 1.0),\n",
       " (601, 1, 1.0),\n",
       " (602, 11, 1.0),\n",
       " (603, 57, 1.0),\n",
       " (604, 14, 1.0),\n",
       " (605, 11, 0.9999999999999999),\n",
       " (606, 11, 0.9999999999999999),\n",
       " (607, 80, 0.9999999999999999),\n",
       " (608, 93, 1.0),\n",
       " (609, 90, 1.0),\n",
       " (610, 0, 0.5312500000000421),\n",
       " (610, 50, 0.4687499999999579),\n",
       " (611, 56, 1.0),\n",
       " (612, 9, 1.0),\n",
       " (613, 95, 1.0),\n",
       " (614, 60, 1.0),\n",
       " (615, 57, 1.0),\n",
       " (616, 43, 1.0),\n",
       " (617, 79, 1.0),\n",
       " (618, 1, 1.0),\n",
       " (619, 41, 0.9999999999999999),\n",
       " (620, 78, 1.0),\n",
       " (621, 0, 1.0),\n",
       " (622, 98, 1.0),\n",
       " (623, 74, 0.9999999999999999),\n",
       " (624, 77, 1.0),\n",
       " (625, 46, 1.0),\n",
       " (626, 32, 1.0),\n",
       " (627, 2, 1.0),\n",
       " (628, 82, 1.0),\n",
       " (629, 61, 0.9999999999999999),\n",
       " (630, 94, 0.28571428571427954),\n",
       " (630, 14, 0.7142857142857204),\n",
       " (631, 9, 0.9999999999999999),\n",
       " (632, 32, 1.0),\n",
       " (633, 50, 1.0),\n",
       " (634, 23, 0.9999999999999999),\n",
       " (635, 29, 1.0),\n",
       " (636, 20, 1.0),\n",
       " (637, 39, 0.9999999999999999),\n",
       " (638, 25, 0.9999999999999999),\n",
       " (639, 29, 1.0),\n",
       " (640, 42, 1.0),\n",
       " (641, 80, 1.0),\n",
       " (642, 72, 1.0),\n",
       " (643, 11, 1.0),\n",
       " (644, 18, 1.0),\n",
       " (645, 9, 1.0),\n",
       " (646, 47, 1.0),\n",
       " (647, 56, 1.0),\n",
       " (648, 47, 1.0),\n",
       " (649, 64, 1.0),\n",
       " (650, 46, 1.0),\n",
       " (651, 45, 1.0),\n",
       " (652, 15, 1.0),\n",
       " (653, 94, 1.0),\n",
       " (654, 9, 1.0),\n",
       " (655, 72, 1.0),\n",
       " (656, 67, 0.9999999999999999),\n",
       " (657, 47, 1.0),\n",
       " (658, 34, 1.0),\n",
       " (659, 68, 1.0),\n",
       " (660, 53, 1.0),\n",
       " (661, 30, 1.0),\n",
       " (662, 17, 1.0),\n",
       " (663, 5, 0.9999999999999999),\n",
       " (664, 23, 1.0),\n",
       " (665, 33, 1.0),\n",
       " (666, 47, 1.0),\n",
       " (667, 80, 1.0),\n",
       " (668, 9, 1.0),\n",
       " (669, 60, 1.0),\n",
       " (670, 17, 1.0),\n",
       " (671, 43, 1.0),\n",
       " (672, 43, 0.9999999999999999),\n",
       " (673, 16, 1.0),\n",
       " (674, 75, 1.0),\n",
       " (675, 1, 1.0),\n",
       " (676, 3, 1.0),\n",
       " (677, 94, 1.0),\n",
       " (678, 31, 1.0),\n",
       " (679, 22, 1.0),\n",
       " (680, 26, 1.0),\n",
       " (681, 60, 1.0),\n",
       " (682, 14, 1.0),\n",
       " (683, 39, 1.0),\n",
       " (684, 25, 0.9999999999999999),\n",
       " (685, 33, 0.9999999999999999),\n",
       " (686, 17, 1.0),\n",
       " (687, 50, 1.0),\n",
       " (688, 87, 0.9999999999999999),\n",
       " (689, 66, 1.0),\n",
       " (690, 37, 1.0),\n",
       " (691, 7, 1.0),\n",
       " (692, 12, 1.0),\n",
       " (693, 7, 1.0),\n",
       " (694, 95, 1.0),\n",
       " (695, 7, 1.0),\n",
       " (696, 68, 1.0),\n",
       " (697, 84, 1.0),\n",
       " (698, 9, 0.9999999999999999),\n",
       " (699, 34, 0.9999999999999999),\n",
       " (700, 13, 1.0),\n",
       " (701, 69, 0.9999999999999999),\n",
       " (702, 6, 1.0),\n",
       " (703, 55, 0.9999999999999999),\n",
       " (704, 59, 1.0),\n",
       " (705, 13, 1.0),\n",
       " (706, 94, 0.9999999999999999),\n",
       " (707, 17, 1.0),\n",
       " (708, 45, 1.0),\n",
       " (709, 97, 1.0),\n",
       " (710, 38, 1.0),\n",
       " (711, 13, 1.0),\n",
       " (712, 35, 1.0),\n",
       " (713, 24, 1.0),\n",
       " (714, 9, 0.9999999999999999),\n",
       " (715, 57, 1.0),\n",
       " (716, 48, 1.0),\n",
       " (717, 6, 1.0),\n",
       " (718, 30, 1.0),\n",
       " (719, 31, 1.0),\n",
       " (720, 52, 1.0),\n",
       " (721, 44, 1.0),\n",
       " (722, 18, 1.0),\n",
       " (723, 91, 1.0),\n",
       " (724, 80, 0.8000000000000225),\n",
       " (724, 56, 0.19999999999997753),\n",
       " (725, 68, 1.0),\n",
       " (726, 17, 1.0),\n",
       " (727, 41, 1.0),\n",
       " (728, 5, 1.0),\n",
       " (729, 31, 1.0),\n",
       " (730, 16, 1.0),\n",
       " (731, 67, 0.9999999999999999),\n",
       " (732, 91, 1.0),\n",
       " (733, 49, 1.0),\n",
       " (734, 7, 1.0),\n",
       " (735, 16, 1.0),\n",
       " (736, 78, 1.0),\n",
       " (737, 11, 1.0),\n",
       " (738, 49, 1.0),\n",
       " (739, 64, 1.0),\n",
       " (740, 0, 1.0),\n",
       " (741, 80, 0.9999999999999999),\n",
       " (742, 98, 1.0),\n",
       " (743, 64, 1.0),\n",
       " (744, 40, 1.0),\n",
       " (745, 24, 1.0),\n",
       " (746, 59, 1.0),\n",
       " (747, 24, 1.0),\n",
       " (748, 45, 1.0),\n",
       " (749, 64, 1.0),\n",
       " (750, 95, 1.0),\n",
       " (751, 53, 1.0),\n",
       " (752, 35, 1.0),\n",
       " (753, 29, 0.9999999999999999),\n",
       " (754, 35, 1.0),\n",
       " (755, 11, 1.0),\n",
       " (756, 3, 0.9999999999999999),\n",
       " (757, 72, 1.0),\n",
       " (758, 21, 1.0),\n",
       " (759, 96, 0.9999999999999999),\n",
       " (760, 22, 1.0),\n",
       " (761, 47, 0.9999999999999999),\n",
       " (762, 86, 1.0),\n",
       " (763, 16, 1.0),\n",
       " (764, 3, 1.0),\n",
       " (765, 31, 1.0),\n",
       " (766, 15, 0.9999999999999999),\n",
       " (767, 81, 0.9999999999999999),\n",
       " (768, 91, 1.0),\n",
       " (769, 43, 1.0),\n",
       " (770, 24, 1.0),\n",
       " (771, 90, 1.0),\n",
       " (772, 11, 1.0),\n",
       " (773, 1, 1.0),\n",
       " (774, 25, 1.0),\n",
       " (775, 98, 1.0),\n",
       " (776, 83, 1.0),\n",
       " (777, 45, 1.0),\n",
       " (778, 2, 1.0),\n",
       " (779, 66, 1.0),\n",
       " (780, 76, 1.0),\n",
       " (781, 8, 1.0),\n",
       " (782, 66, 1.0),\n",
       " (783, 51, 1.0),\n",
       " (784, 74, 1.0),\n",
       " (785, 55, 1.0),\n",
       " (786, 95, 0.9999999999999999),\n",
       " (787, 5, 1.0),\n",
       " (788, 14, 1.0),\n",
       " (789, 51, 1.0),\n",
       " (790, 58, 1.0),\n",
       " (791, 4, 0.9999999999999999),\n",
       " (792, 87, 1.0),\n",
       " (793, 99, 1.0),\n",
       " (794, 31, 1.0),\n",
       " (795, 29, 1.0),\n",
       " (796, 80, 1.0),\n",
       " (797, 0, 1.0),\n",
       " (798, 34, 1.0),\n",
       " (799, 2, 1.0),\n",
       " (800, 56, 1.0),\n",
       " (801, 16, 1.0),\n",
       " (802, 12, 1.0),\n",
       " (803, 18, 1.0),\n",
       " (804, 56, 1.0),\n",
       " (805, 10, 1.0),\n",
       " (806, 48, 1.0),\n",
       " (807, 71, 1.0),\n",
       " (808, 51, 0.9999999999999999),\n",
       " (809, 1, 1.0),\n",
       " (810, 68, 0.9999999999999999),\n",
       " (811, 74, 1.0),\n",
       " (812, 94, 1.0),\n",
       " (813, 52, 1.0),\n",
       " (814, 26, 1.0),\n",
       " (815, 0, 1.0),\n",
       " (816, 53, 1.0),\n",
       " (817, 52, 1.0),\n",
       " (818, 3, 1.0),\n",
       " (819, 31, 1.0),\n",
       " (820, 89, 1.0),\n",
       " (821, 35, 1.0),\n",
       " (822, 33, 1.0),\n",
       " (823, 34, 0.9999999999999999),\n",
       " (824, 7, 1.0),\n",
       " (825, 28, 1.0),\n",
       " (826, 27, 1.0),\n",
       " (827, 70, 1.0),\n",
       " (828, 79, 1.0),\n",
       " (829, 69, 0.9999999999999999),\n",
       " (830, 35, 1.0),\n",
       " (831, 7, 1.0),\n",
       " (832, 40, 1.0),\n",
       " (833, 0, 1.0),\n",
       " (834, 55, 0.9999999999999999),\n",
       " (835, 16, 0.9999999999999999),\n",
       " (836, 30, 1.0),\n",
       " (837, 86, 1.0),\n",
       " (838, 93, 1.0),\n",
       " (839, 11, 1.0),\n",
       " (840, 23, 1.0),\n",
       " (841, 91, 1.0),\n",
       " (842, 68, 1.0),\n",
       " (843, 13, 1.0),\n",
       " (844, 68, 1.0),\n",
       " (845, 4, 1.0),\n",
       " (846, 75, 1.0),\n",
       " (847, 94, 1.0),\n",
       " (848, 41, 1.0),\n",
       " (849, 49, 1.0),\n",
       " (850, 18, 1.0),\n",
       " (851, 12, 1.0),\n",
       " (852, 30, 1.0),\n",
       " (853, 54, 1.0),\n",
       " (854, 13, 1.0),\n",
       " (855, 50, 1.0),\n",
       " (856, 69, 1.0),\n",
       " (857, 10, 1.0),\n",
       " (858, 0, 1.0),\n",
       " (859, 8, 1.0),\n",
       " (860, 54, 1.0),\n",
       " (861, 56, 1.0),\n",
       " (862, 0, 1.0),\n",
       " (863, 81, 1.0),\n",
       " (864, 3, 1.0),\n",
       " (865, 18, 1.0),\n",
       " (866, 23, 1.0),\n",
       " (867, 2, 1.0),\n",
       " (868, 32, 1.0),\n",
       " (869, 10, 0.9999999999999999),\n",
       " (870, 56, 1.0),\n",
       " (871, 99, 1.0),\n",
       " (872, 10, 1.0),\n",
       " (873, 4, 1.0),\n",
       " (874, 22, 1.0),\n",
       " (875, 81, 1.0),\n",
       " (876, 96, 1.0),\n",
       " (877, 62, 1.0),\n",
       " (878, 3, 1.0),\n",
       " (879, 64, 1.0),\n",
       " (880, 52, 1.0),\n",
       " (881, 40, 1.0),\n",
       " (882, 46, 0.9999999999999999),\n",
       " (883, 0, 1.0),\n",
       " (884, 32, 1.0),\n",
       " (885, 5, 0.9999999999999999),\n",
       " (886, 80, 0.9999999999999999),\n",
       " (887, 82, 1.0),\n",
       " (888, 29, 1.0),\n",
       " (889, 98, 1.0),\n",
       " (890, 64, 1.0),\n",
       " (891, 0, 1.0),\n",
       " (892, 0, 1.0),\n",
       " (893, 62, 1.0),\n",
       " (894, 77, 1.0),\n",
       " (895, 43, 1.0),\n",
       " (896, 28, 1.0),\n",
       " (897, 0, 1.0),\n",
       " (898, 25, 1.0),\n",
       " (899, 80, 1.0),\n",
       " (900, 72, 1.0),\n",
       " (901, 6, 1.0),\n",
       " (902, 32, 1.0),\n",
       " (903, 18, 1.0),\n",
       " (904, 23, 1.0),\n",
       " (905, 4, 1.0),\n",
       " (906, 72, 0.9999999999999999),\n",
       " (907, 33, 1.0),\n",
       " (908, 89, 1.0),\n",
       " (909, 35, 1.0),\n",
       " (910, 45, 1.0),\n",
       " (911, 9, 1.0),\n",
       " (912, 67, 1.0),\n",
       " (913, 58, 1.0),\n",
       " (914, 93, 1.0),\n",
       " (915, 54, 1.0),\n",
       " (916, 80, 1.0),\n",
       " (917, 59, 1.0),\n",
       " (918, 10, 1.0),\n",
       " (919, 98, 1.0),\n",
       " (920, 25, 0.9999999999999999),\n",
       " (921, 30, 1.0),\n",
       " (922, 5, 1.0),\n",
       " (923, 50, 1.0),\n",
       " (924, 42, 1.0),\n",
       " (925, 70, 0.9999999999999999),\n",
       " (926, 32, 0.8333333333333472),\n",
       " (926, 17, 0.16666666666665278),\n",
       " (927, 73, 1.0),\n",
       " (928, 85, 0.9999999999999999),\n",
       " (929, 68, 0.9999999999999999),\n",
       " (930, 1, 1.0),\n",
       " (931, 34, 1.0),\n",
       " (932, 11, 1.0),\n",
       " (933, 72, 1.0),\n",
       " (934, 37, 1.0),\n",
       " (935, 25, 1.0),\n",
       " (936, 30, 0.9999999999999999),\n",
       " (937, 26, 1.0),\n",
       " (938, 45, 1.0),\n",
       " (939, 36, 1.0),\n",
       " (940, 30, 1.0),\n",
       " (941, 22, 0.2500000000000032),\n",
       " (941, 89, 0.7499999999999968),\n",
       " (942, 56, 0.9999999999999999),\n",
       " (943, 81, 1.0),\n",
       " (944, 86, 1.0),\n",
       " (945, 21, 1.0),\n",
       " (946, 71, 1.0),\n",
       " (947, 27, 1.0),\n",
       " (948, 83, 1.0),\n",
       " (949, 85, 1.0),\n",
       " (950, 19, 1.0),\n",
       " (951, 87, 1.0),\n",
       " (952, 53, 1.0),\n",
       " (953, 45, 0.9999999999999999),\n",
       " (954, 79, 1.0),\n",
       " (955, 62, 1.0),\n",
       " (956, 15, 1.0),\n",
       " (957, 15, 1.0),\n",
       " (958, 23, 1.0),\n",
       " (959, 41, 1.0),\n",
       " (960, 49, 1.0),\n",
       " (961, 52, 0.33333333333333826),\n",
       " (961, 57, 0.6666666666666617),\n",
       " (962, 43, 1.0),\n",
       " (963, 32, 1.0),\n",
       " (964, 0, 1.0),\n",
       " (965, 60, 1.0),\n",
       " (966, 5, 1.0),\n",
       " (967, 62, 1.0),\n",
       " (968, 1, 1.0),\n",
       " (969, 85, 1.0),\n",
       " (970, 96, 1.0),\n",
       " (971, 12, 1.0),\n",
       " (972, 89, 1.0),\n",
       " (973, 81, 1.0),\n",
       " (974, 43, 1.0),\n",
       " (975, 0, 1.0),\n",
       " (976, 17, 1.0),\n",
       " (977, 53, 0.9999999999999999),\n",
       " (978, 58, 1.0),\n",
       " (979, 3, 1.0),\n",
       " (980, 37, 1.0),\n",
       " (981, 11, 1.0),\n",
       " (982, 13, 0.9999999999999999),\n",
       " (983, 95, 1.0),\n",
       " (984, 1, 1.0),\n",
       " (985, 43, 0.9999999999999999),\n",
       " (986, 75, 1.0),\n",
       " (987, 40, 1.0),\n",
       " (988, 10, 1.0),\n",
       " ...]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "value = [(i,j,x[i,j].solution_value()) for i in range(N_FAMILY) for j in DISIRED[i,:] if x[i,j].solution_value()>0]\n",
    "value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:59.627448Z",
     "start_time": "2020-11-29T07:01:59.605447Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>family_id</th>\n",
       "      <th>day</th>\n",
       "      <th>result</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>51</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>25</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>99</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td>52</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5068</th>\n",
       "      <td>4995</td>\n",
       "      <td>15</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5069</th>\n",
       "      <td>4996</td>\n",
       "      <td>87</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5070</th>\n",
       "      <td>4997</td>\n",
       "      <td>31</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5071</th>\n",
       "      <td>4998</td>\n",
       "      <td>91</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5072</th>\n",
       "      <td>4999</td>\n",
       "      <td>12</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>5073 rows × 3 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "      family_id  day  result\n",
       "0             0   51     1.0\n",
       "1             1   25     1.0\n",
       "2             2   99     1.0\n",
       "3             3    1     1.0\n",
       "4             4   52     1.0\n",
       "...         ...  ...     ...\n",
       "5068       4995   15     1.0\n",
       "5069       4996   87     1.0\n",
       "5070       4997   31     1.0\n",
       "5071       4998   91     1.0\n",
       "5072       4999   12     1.0\n",
       "\n",
       "[5073 rows x 3 columns]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_result=pd.DataFrame(value, columns=['family_id','day','result'])\n",
    "df_result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:59.639449Z",
     "start_time": "2020-11-29T07:01:59.630448Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.000000    4301\n",
       "1.000000     627\n",
       "0.750000       2\n",
       "0.666667       2\n",
       "0.666667       2\n",
       "            ... \n",
       "0.750000       1\n",
       "0.400000       1\n",
       "0.400000       1\n",
       "0.400000       1\n",
       "0.947917       1\n",
       "Name: result, Length: 144, dtype: int64"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#从上面的结果中看出多出了81个，通过value_counts查看下结果,发现有一些小数值\n",
    "df_result.result.value_counts()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:59.678451Z",
     "start_time": "2020-11-29T07:01:59.642449Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>family_id</th>\n",
       "      <th>day</th>\n",
       "      <th>result</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>51</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>25</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>99</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td>52</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5068</th>\n",
       "      <td>4995</td>\n",
       "      <td>15</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5069</th>\n",
       "      <td>4996</td>\n",
       "      <td>87</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5070</th>\n",
       "      <td>4997</td>\n",
       "      <td>31</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5071</th>\n",
       "      <td>4998</td>\n",
       "      <td>91</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5072</th>\n",
       "      <td>4999</td>\n",
       "      <td>12</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>4931 rows × 3 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "      family_id  day  result\n",
       "0             0   51     1.0\n",
       "1             1   25     1.0\n",
       "2             2   99     1.0\n",
       "3             3    1     1.0\n",
       "4             4   52     1.0\n",
       "...         ...  ...     ...\n",
       "5068       4995   15     1.0\n",
       "5069       4996   87     1.0\n",
       "5070       4997   31     1.0\n",
       "5071       4998   91     1.0\n",
       "5072       4999   12     1.0\n",
       "\n",
       "[4931 rows x 3 columns]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#结果是1的作为可接受的结果，非1的需要通过整数规划器重新寻求解\n",
    "thresold = 0.999999999\n",
    "df_assinged=df_result[df_result['result']>thresold]\n",
    "df_assinged"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:59.695452Z",
     "start_time": "2020-11-29T07:01:59.680451Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>family_id</th>\n",
       "      <th>day</th>\n",
       "      <th>result</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>59</th>\n",
       "      <td>59</td>\n",
       "      <td>38</td>\n",
       "      <td>0.25</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>60</th>\n",
       "      <td>59</td>\n",
       "      <td>14</td>\n",
       "      <td>0.75</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>241</th>\n",
       "      <td>240</td>\n",
       "      <td>32</td>\n",
       "      <td>0.75</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>242</th>\n",
       "      <td>240</td>\n",
       "      <td>56</td>\n",
       "      <td>0.25</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>264</th>\n",
       "      <td>262</td>\n",
       "      <td>31</td>\n",
       "      <td>0.50</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4983</th>\n",
       "      <td>4912</td>\n",
       "      <td>8</td>\n",
       "      <td>0.40</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4985</th>\n",
       "      <td>4914</td>\n",
       "      <td>38</td>\n",
       "      <td>0.60</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4986</th>\n",
       "      <td>4914</td>\n",
       "      <td>43</td>\n",
       "      <td>0.40</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5033</th>\n",
       "      <td>4961</td>\n",
       "      <td>53</td>\n",
       "      <td>0.75</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5034</th>\n",
       "      <td>4961</td>\n",
       "      <td>15</td>\n",
       "      <td>0.25</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>138 rows × 3 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "      family_id  day  result\n",
       "59           59   38    0.25\n",
       "60           59   14    0.75\n",
       "241         240   32    0.75\n",
       "242         240   56    0.25\n",
       "264         262   31    0.50\n",
       "...         ...  ...     ...\n",
       "4983       4912    8    0.40\n",
       "4985       4914   38    0.60\n",
       "4986       4914   43    0.40\n",
       "5033       4961   53    0.75\n",
       "5034       4961   15    0.25\n",
       "\n",
       "[138 rows x 3 columns]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_unassinged=df_result[(df_result['result']<=thresold) & (df_result['result']>=1-thresold)]\n",
    "df_unassinged"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用MIP再次求解未被assign的家庭"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:59.712453Z",
     "start_time": "2020-11-29T07:01:59.698452Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "day\n",
      "0     290\n",
      "1     271\n",
      "2     294\n",
      "3     293\n",
      "4     263\n",
      "     ... \n",
      "95    158\n",
      "96    128\n",
      "97    125\n",
      "98    122\n",
      "99    124\n",
      "Name: family_size, Length: 100, dtype: int64\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\ProgramData\\Anaconda3\\lib\\site-packages\\ipykernel_launcher.py:2: SettingWithCopyWarning: \n",
      "A value is trying to be set on a copy of a slice from a DataFrame.\n",
      "Try using .loc[row_indexer,col_indexer] = value instead\n",
      "\n",
      "See the caveats in the documentation: https://pandas.pydata.org/pandas-docs/stable/user_guide/indexing.html#returning-a-view-versus-a-copy\n",
      "  \n"
     ]
    }
   ],
   "source": [
    "#计算每天被安排的人数\n",
    "df_assinged['family_size'] = FAMILY_SIZE[df_assinged.family_id]\n",
    "occupancy = df_assinged.groupby('day')['family_size'].sum()\n",
    "print(occupancy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:59.723454Z",
     "start_time": "2020-11-29T07:01:59.714453Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
      " 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4 0 0 0 0 0 2 0 0 0 0\n",
      " 0 0 4 0 0 0 0 0 0 5 0 0 0 0 0 0 0 3 0 0 0 0 0 0 3 1]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([ 10,  29,   6,   7,  37,  58,  77,  53,  27,   3,  12,   8,  25,\n",
       "        50,  62,  28,   8,   8,  29,  52,  77,  56,  36,   9,   8,   4,\n",
       "        27,  51,  66,  49,  22,  17,  48,  65,  95, 116,  98,  67,  47,\n",
       "        69,  90, 117,  96,  71,  53,  19,  44,  77,  96, 102,  78,  52,\n",
       "        45,  77,  92, 115, 127, 104,  81, 102, 126, 159, 176, 179, 151,\n",
       "       130, 122, 142, 164, 177, 175, 165, 142, 115, 142, 165, 179, 175,\n",
       "       158, 133, 114, 133, 162, 180, 172, 145, 126,  97, 123, 148, 170,\n",
       "       178, 170, 142, 122, 142, 172, 175, 178, 176])"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#经过第1轮线性规划器安排后，每天可以被安排人数的上下限\n",
    "min_occupancy=np.array([max(0,MIN_OCCUPANCY-i) for i in occupancy])\n",
    "max_occupancy=np.array([max(0,MAX_OCCUPANCY-i) for i in occupancy])\n",
    "print(min_occupancy)\n",
    "max_occupancy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用整数规划进行求解"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:59.885463Z",
     "start_time": "2020-11-29T07:01:59.726454Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>family_id</th>\n",
       "      <th>day</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>59</td>\n",
       "      <td>38</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>240</td>\n",
       "      <td>32</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>262</td>\n",
       "      <td>31</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>357</td>\n",
       "      <td>24</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>488</td>\n",
       "      <td>39</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>64</th>\n",
       "      <td>4869</td>\n",
       "      <td>59</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>65</th>\n",
       "      <td>4886</td>\n",
       "      <td>98</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>66</th>\n",
       "      <td>4912</td>\n",
       "      <td>17</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>67</th>\n",
       "      <td>4914</td>\n",
       "      <td>38</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>68</th>\n",
       "      <td>4961</td>\n",
       "      <td>53</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>69 rows × 2 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "    family_id  day\n",
       "0          59   38\n",
       "1         240   32\n",
       "2         262   31\n",
       "3         357   24\n",
       "4         488   39\n",
       "..        ...  ...\n",
       "64       4869   59\n",
       "65       4886   98\n",
       "66       4912   17\n",
       "67       4914   38\n",
       "68       4961   53\n",
       "\n",
       "[69 rows x 2 columns]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#创建CBC求解器\n",
    "solver = pywraplp.Solver(\"AssignmentProblem\", pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)\n",
    "\n",
    "x = {}  # family_id在第j天是否参观\n",
    "# 每一天有哪些家庭,有100天，每一天的家庭\n",
    "candidates = [[] for x in range(N_DAY)]\n",
    "\n",
    "#没有被安排的家庭\n",
    "families = df_unassinged['family_id'].unique()\n",
    "\n",
    "for i in families:  # family_id\n",
    "    for j in DISIRED[i, :]:  # family_id的choice\n",
    "        candidates[j].append(i)  # 在第j天，有第i个family参观\n",
    "        # 定义决策变量x[i,j],i代表family_id, j代表第j天参观\n",
    "        x[i, j] = solver.BoolVar('x[%i,%i]' % (i, j))\n",
    "\n",
    "#定义目标函数preference cost部分,每个家庭在所有期望日的成本累加\n",
    "preference_cost= solver.Sum(x[i,j] * pcost_matrix[i,j] for i in families for j in DISIRED[i,:])\n",
    "\n",
    "#满足preference cost最小\n",
    "solver.Minimize((preference_cost))\n",
    "\n",
    "#增加约束条件1，人数要在min_occupancy和max_occupancy之间\n",
    "FAMILY_SIZE=data['n_people'].values\n",
    "daily_occupancy =[solver.Sum(x[i,j] * FAMILY_SIZE[i] for i in candidates[j]) for j in range(N_DAY)]\n",
    "\n",
    "for j in range(N_DAY):   #j代表当天，j+1代表前一天\n",
    "    solver.Add(daily_occupancy[j]>=min_occupancy[j])  \n",
    "    solver.Add(daily_occupancy[j]<=max_occupancy[j])\n",
    "    \n",
    "#加约束条件2，每个家庭在choice里只出现1次    \n",
    "family_presence = [solver.Sum(x[i,j] for j in DISIRED[i,:]) for i in families]\n",
    "n_familes = len(families)\n",
    "for i in range(n_familes):\n",
    "    solver.Add(family_presence[i]==1)\n",
    "\n",
    "\n",
    "result = solver.Solve()\n",
    "\n",
    "temp = [(i, j) for i in families for j in DISIRED[i, :] if x[i, j].solution_value() > 0]\n",
    "#计算剩余家庭安排\n",
    "df_mip = pd.DataFrame(temp, columns= ['family_id', 'day'])\n",
    "df_mip"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "安排结果合并"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:59.898464Z",
     "start_time": "2020-11-29T07:01:59.887463Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "      family_id  day\n",
      "0             0   51\n",
      "1             1   25\n",
      "2             2   99\n",
      "3             3    1\n",
      "4             4   52\n",
      "...         ...  ...\n",
      "5068       4995   15\n",
      "5069       4996   87\n",
      "5070       4997   31\n",
      "5071       4998   91\n",
      "5072       4999   12\n",
      "\n",
      "[5000 rows x 2 columns]\n"
     ]
    }
   ],
   "source": [
    "#数据合并\n",
    "df = pd.concat((df_assinged[['family_id','day']], df_mip)).sort_values('family_id')\n",
    "print(df)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. 计算preference cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:59.907464Z",
     "start_time": "2020-11-29T07:01:59.901464Z"
    }
   },
   "outputs": [],
   "source": [
    "#根据安排情况，计算这个安排的preference cost\n",
    "def pcost(predictions):\n",
    "    daily_occupancy = np.zeros(N_DAY+1, dtype=np.int64)\n",
    "    penalty=0\n",
    "    for (i,p) in enumerate(predictions):\n",
    "        #计算家庭人数\n",
    "        n = FAMILY_SIZE[i]\n",
    "        #第i个家庭，p天访问时的cost\n",
    "        penalty +=pcost_matrix[i,p]\n",
    "        #计算当天的人数\n",
    "        daily_occupancy[p] += n\n",
    "\n",
    "    return penalty,daily_occupancy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5.计算accounting cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:59.915465Z",
     "start_time": "2020-11-29T07:01:59.910464Z"
    }
   },
   "outputs": [],
   "source": [
    "#根据安排情况，计算安排的accounting cost\n",
    "def acost(daily_occupancy):\n",
    "    accounting_cost = 0\n",
    "    num_out_of_range = 0\n",
    "    for day in range(N_DAY):\n",
    "        n_p1 = daily_occupancy[day+1]  #前一天\n",
    "        n = daily_occupancy[day]       #当天\n",
    "\n",
    "        #如果超过了承载范围，则设置 out_of_range\n",
    "        num_out_of_range += (n>MAX_OCCUPANCY) or (n<MIN_OCCUPANCY)\n",
    "\n",
    "        #计算accounting cost\n",
    "        accounting_cost += acost_matrix[n,n_p1]\n",
    "\n",
    "    return accounting_cost, num_out_of_range"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6.计算cost function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:59.922465Z",
     "start_time": "2020-11-29T07:01:59.917465Z"
    }
   },
   "outputs": [],
   "source": [
    "#根据安排prediction，计算cost function\n",
    "def cost_function(prediction):\n",
    "    #基于predcition计算preference cost和accounting cost\n",
    "    penalty, daily_occupancy = pcost(prediction)  #计算preference cost和每天承载数量\n",
    "    accounting_cost, num_out_of_range = acost(daily_occupancy) #根据每天承载数量计算accounting cost\n",
    "    print(\"num_out_of_range=\",num_out_of_range)\n",
    "    final_score = penalty + accounting_cost + num_out_of_range*99999999   #最后一项是对越界的惩罚\n",
    "    return final_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-29T07:01:59.937466Z",
     "start_time": "2020-11-29T07:01:59.924465Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "num_out_of_range= 0\n",
      "109264.37486476195\n"
     ]
    }
   ],
   "source": [
    "prediction = df.day.values\n",
    "print(cost_function(prediction))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
